// https://leetcode.cn/problems/ugly-number-ii/
// Created by ade on 2022/9/14.
// 给你一个整数 n ，请你找出并返回第 n 个 丑数 。 1 <= n <= 1690
// 输入：n = 10
// 输出：12
// 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
/*
 * 2 3 5
 * 4  6  10  *2
 * 6  9  15  *3
 * 10 15 25  *5
 * */
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // 思路：丑数肯定都是2,3,5的倍数，三个指针p2,p3,p5对应指针，每次找到三个指针最小的丑数，时间和空间复杂度都是O(N)
    int nthUglyNumber(int n) {
        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = min(min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5);
            if (dp[i] == dp[p2] * 2) p2++;
            if (dp[i] == dp[p3] * 3) p3++;
            if (dp[i] == dp[p5] * 5) p5++;
        }
        return dp[n];
    }

};

int main() {
    Solution so;
    cout << so.nthUglyNumber(10);
    return 0;
}

